#include <iostream>
#include <vector>
#include <map>

using namespace std;

// 208. 实现Trie(前缀树)
// 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
// 这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

class Trie {
private:
    struct TrieNode {
        bool isWord = false;
        map<char, TrieNode*> children;
    };
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* ws = root;
        for(int i = 0; i < word.size(); i++) {
            char c = word[i];
            if(ws->children[c - 'a'] == nullptr) {
                ws->children[c - 'a'] = new TrieNode();
            }
        }
    }

    bool search(string word) {

    }

    bool startsWith(string prefix) {

    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
